package leetcode.D100.T56;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: DYZ
 * @Create: 2021-08-12 16:12:41 星期四
 */

public class Solution {
    // 一刷
    /*public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        List<int[]> result = new ArrayList<>();
        for(int i=0; i<intervals.length; ++i) {
            int size = result.size();
            if(size == 0 || intervals[i][0] > result.get(size-1)[1]) {
                result.add(intervals[i]);
            } else {
                result.get(size-1)[1] = Math.max(result.get(size-1)[1], intervals[i][1]);
            }
        }
        return result.toArray(new int[result.size()][2]);
    }*/

    // 二刷
    /*public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (o1, o2) -> {
            if (o1[0] != o2[0])
                return o1[0] - o2[0];
            return o2[1] - o1[1];
        });
        int left = intervals[0][0], right = intervals[0][1];
        List<int[]> results = new ArrayList<>();
        for (int i = 1; i < intervals.length; i++) {
            int[] interval = intervals[i];
            if (interval[0] > right) {
                results.add(new int[] {left, right});
                left = interval[0];
                right = interval[1];
            } else if (interval[1] > right) {
                right = interval[1];
            }
        }
        results.add(new int[]{left, right});
        return results.toArray(new int[results.size()][2]);
    }*/

    // 三刷
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] != b[0])
                return a[0] - b[0];
            else
                return a[1] - b[1];
        });
        int first = intervals[0][0], last = intervals[0][1];
        List<int[]> result = new ArrayList<>();
        for (int i=1; i<intervals.length; ++i) {
            int[] interval = intervals[i];
            if (interval[0] <= last) {
                last = Math.max(last, interval[1]);
            } else {
                result.add(new int[] {first, last});
                first = interval[0];
                last = interval[1];
            }
        }
        result.add(new int[] {first, last});
        return result.toArray(new int[result.size()][2]);
    }
}
